package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

public class HeapPermutations {

    /**
     * 递归生成全排列（Heap算法）
     * @param array 待排列的数组
     * @param last 当前处理的最后一个元素索引
     * @param result 存储排列结果的列表
     * @param <T> 元素类型
     */
    private static <T> void recursive(List<T> array, int last, List<List<T>> result) {
        // 递归终止条件：处理到第一个元素，记录当前排列
        if (last == 0) {
            result.add(new ArrayList<>(array)); // 拷贝当前数组，避免后续修改影响结果
            return;
        }

        // 循环处理每个位置，生成排列
        for (int i = 0; i <= last; i++) {
            // 递归处理前last个元素
            recursive(array, last - 1, result);

            // 根据last的奇偶性执行不同的交换逻辑
            if (last % 2 == 0) {
                // 偶数：交换第一个元素和最后一个元素
                swap(array, 0, last);
            } else {
                // 奇数：交换第i个元素和最后一个元素
                swap(array, i, last);
            }
        }
    }

    /**
     * 交换列表中指定索引的两个元素
     * @param list 列表
     * @param i 索引1
     * @param j 索引2
     * @param <T> 元素类型
     */
    private static <T> void swap(List<T> list, int i, int j) {
        T temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    /**
     * 生成输入列表的全排列
     * @param array 原始列表
     * @return 全排列结果
     * @param <T> 元素类型
     */
    public static <T> List<List<T>> permutations(List<T> array) {
        List<List<T>> result = new ArrayList<>();
        // 拷贝原始数组，避免修改原数组
        List<T> copyArray = new ArrayList<>(array);
        recursive(copyArray, copyArray.size() - 1, result);
        return result;
    }

    public static void main(String[] args) {
        // 测试：生成[A,B,C,D]的全排列
        List<String> array = new ArrayList<>();
        array.add("A");
        array.add("B");
        array.add("C");
        array.add("D");

        List<List<String>> result = permutations(array);
        // 输出所有排列
        for (List<String> perm : result) {
            System.out.println(perm);
        }
    }
}